{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if There is a Valid Partition For The Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validPartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查数组是否存在有效划分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，你必须将数组划分为一个或多个 <strong>连续</strong> 子数组。</p>\n",
    "\n",
    "<p>如果获得的这些子数组中每个都能满足下述条件<strong> 之一</strong> ，则可以称其为数组的一种 <strong>有效</strong> 划分：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>子数组 <strong>恰</strong> 由 <code>2</code> 个相等元素组成，例如，子数组 <code>[2,2]</code> 。</li>\n",
    "\t<li>子数组 <strong>恰</strong> 由 <code>3</code> 个相等元素组成，例如，子数组 <code>[4,4,4]</code> 。</li>\n",
    "\t<li>子数组 <strong>恰</strong> 由 <code>3</code> 个连续递增元素组成，并且相邻元素之间的差值为 <code>1</code> 。例如，子数组 <code>[3,4,5]</code> ，但是子数组 <code>[1,3,5]</code> 不符合要求。</li>\n",
    "</ol>\n",
    "\n",
    "<p>如果数组 <strong>至少</strong> 存在一种有效划分，返回 <code>true</code><em> </em>，否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,4,4,5,6]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>数组可以划分成子数组 [4,4] 和 [4,5,6] 。\n",
    "这是一种有效划分，所以返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>该数组不存在有效划分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-there-is-a-valid-partition-for-the-array](https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-there-is-a-valid-partition-for-the-array](https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,4,4,5,6]', '[1,1,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        lastN = nums[0]\n",
    "        llastN = -10\n",
    "        valid, lastValid, llastValid = False, True, False\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            valid, lastValid, llastValid = (n == lastN and lastValid) or \\\n",
    "                    (llastValid and \n",
    "                        (n == lastN == llastN or n - lastN == 1 and lastN - llastN == 1)\n",
    "                    ), valid, lastValid\n",
    "            lastN, llastN = n, lastN\n",
    "        return valid\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        nums_len = len(nums)\n",
    "        if nums_len==2:\n",
    "            return nums[0]==nums[1]\n",
    "        dp = [0]*(nums_len+1)\n",
    "        dp[2] = nums[0] == nums[1]\n",
    "        dp[3] = dp[2] and nums[1] == nums[2]\n",
    "        dp[3] =  dp[3] or (nums[2]-nums[1]==1 and nums[1] - nums[0] ==1)\n",
    "        for i in range(4, nums_len+1):\n",
    "            dp[i] = (dp[i-2] and nums[i-1]==nums[i-2]) or (dp[i-3] and (dp[i-3] and ((nums[i-3]==nums[i-2] and nums[i-2]==nums[i-1]) or (nums[i-2]-nums[i-3]==1 and nums[i-1]-nums[i-2] == 1)  )))\n",
    "        return dp[-1]!=0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#O(n), O(n)\n",
    "# class Solution:\n",
    "#     def validPartition(self, nums: List[int]) -> bool:\n",
    "#         n = len(nums)\n",
    "#         dp = [False] * (n+1)\n",
    "#         dp[0] = True\n",
    "#         if nums[0] == nums[1]:\n",
    "#             dp[2] = True\n",
    "        \n",
    "#         for i in range(3,n+1):\n",
    "#             # check each criteria:\n",
    "#             c1 = nums[i-1] == nums[i-2] and dp[i-2]\n",
    "#             c2 = nums[i-1] == nums[i-2] == nums[i-3] and dp[i-3]\n",
    "#             c3 = nums[i-1]-nums[i-2] == 1 and nums[i-2]-nums[i-3] == 1 and dp[i-3]\n",
    "#             if c1 or c2 or c3:\n",
    "#                 dp[i] = True\n",
    "#         return dp[n]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # p stands for previous\n",
    "        dp0 = True\n",
    "        dp1 = False\n",
    "        dp2 = True if nums[0] == nums[1] else False\n",
    "\n",
    "        for i in range(3,n+1):\n",
    "            c1 = nums[i-1] == nums[i-2] and dp1\n",
    "            c2 = nums[i-1] == nums[i-2] == nums[i-3] and dp0\n",
    "            c3 = nums[i-1]-nums[i-2] == 1 and nums[i-2]-nums[i-3] == 1 and dp0\n",
    "\n",
    "            dp0,dp1 = dp1,dp2\n",
    "            dp2 = c1 or c2 or c3\n",
    "            \n",
    "            \n",
    "        return dp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [False]*(n+1)\n",
    "        dp[0] = True\n",
    "        for i in range(n):\n",
    "            if i-1>=0 and nums[i-1] == nums[i] and dp[i-1]:\n",
    "                dp[i+1] = True\n",
    "            if i-2>=0 and nums[i-2] == nums[i-1] == nums[i] and dp[i-2]:\n",
    "                dp[i+1] = True\n",
    "            if i - 2 >= 0 and nums[i - 2]+2 == nums[i - 1]+1 == nums[i] and dp[i - 2]:\n",
    "                dp[i + 1] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        nums_len = len(nums)\n",
    "        if nums_len==2:\n",
    "            return nums[0]==nums[1]\n",
    "        dp = [0]*(nums_len+1)\n",
    "        dp[2] = nums[0] == nums[1]\n",
    "        dp[3] = dp[2] and nums[1] == nums[2]\n",
    "        dp[3] =  dp[3] or (nums[2]-nums[1]==1 and nums[1] - nums[0] ==1)\n",
    "        for i in range(4, nums_len+1):\n",
    "            dp[i] = (dp[i-2] and nums[i-1]==nums[i-2]) or (dp[i-3] and (dp[i-3] and ((nums[i-3]==nums[i-2] and nums[i-2]==nums[i-1]) or (nums[i-2]-nums[i-3]==1 and nums[i-1]-nums[i-2] == 1)  )))\n",
    "        return dp[-1]!=0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        #定义空数组为f[0]\n",
    "        #f[i+1]表示nums[0]-nums[i]存在一种有效划分\n",
    "        n=len(nums)\n",
    "        f=[False]*(n+1)\n",
    "        f[0]=True\n",
    "        for i in range(1,n):\n",
    "            x=nums[i]\n",
    "            if x==nums[i-1]:\n",
    "                f[i+1]|=f[i-1]\n",
    "            if i>1 and x==nums[i-1]==nums[i-2] or x==nums[i-1]+1==nums[i-2]+2:\n",
    "                f[i+1]|=f[i-2]\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        f=[False]*(n+1)\n",
    "        f[0]=True\n",
    "        for i in range(1,n):\n",
    "            x=nums[i]\n",
    "            if f[i-1] and x==nums[i-1]:\n",
    "                f[i+1]=True\n",
    "            if i>1:\n",
    "                if f[i-2] and (x==nums[i-1]==nums[i-2] or x==nums[i-1]+1==nums[i-2]+2):\n",
    "                    f[i+1]=True\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        #定义空数组为f[0]\n",
    "        #f[i+1]表示nums[0]-nums[i]存在一种有效划分\n",
    "        n=len(nums)\n",
    "        f=[False]*(n+1)\n",
    "        f[0]=True\n",
    "        for i in range(1,n):\n",
    "            x=nums[i]\n",
    "            if x==nums[i-1]:\n",
    "                f[i+1]|=f[i-1]\n",
    "            if f[i+1]:continue\n",
    "            if i>1 and x==nums[i-1]==nums[i-2] or x==nums[i-1]+1==nums[i-2]+2:\n",
    "                f[i+1]|=f[i-2]\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [False]*(n+1)\n",
    "        f[0] = True\n",
    "\n",
    "\n",
    "        \"\"\" for i,x in enumerate(nums):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                f[i+1] = f[i-1]\n",
    "\n",
    "         \n",
    "            elif nums[i] == nums[i-1]+1: \"\"\"\n",
    "        for i in range(n):\n",
    "            if i > 0 and f[i-1] and nums[i] == nums[i-1] or i > 1 and f[i-2] and (nums[i-2]==nums[i-1]==nums[i] or nums[i] == nums[i-1]+1 == nums[i-2]+2):\n",
    "                f[i+1] = True\n",
    "        return f[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [False] * (n+1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            if i >= 1 and nums[i] == nums[i-1]:\n",
    "                dp[i+1] = dp[i-1] \n",
    "            if i >= 2 and ((nums[i] == nums[i-1] and nums[i-1] == nums[i-2]) or (nums[i] == nums[i-1] + 1 and nums[i-1] == nums[i-2] + 1)):\n",
    "                dp[i+1] = dp[i+1] or dp[i-2]\n",
    "\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        if nums[0]==nums[1]:\n",
    "            dp[2]=True\n",
    "        for i in range(3,n+1):\n",
    "            if dp[i-2]:\n",
    "                if nums[i-1]==nums[i-2]:\n",
    "                    dp[i]=True\n",
    "            if dp[i-3]:\n",
    "                if nums[i-1]==nums[i-2]==nums[i-3] or nums[i-3]+2==nums[i-2]+1==nums[i-1]:\n",
    "                    dp[i]=True \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [False]*(n+1)\n",
    "        f[0] = True\n",
    "        for i in range(1,n):\n",
    "            x = nums[i]\n",
    "            if f[i-1] and x==nums[i-1]:\n",
    "                f[i+1] = True\n",
    "            if i > 1:\n",
    "                if f[i-2] and x == nums[i-1] == nums[i-2]:\n",
    "                    f[i+1] = True\n",
    "                if f[i-2] and x == nums[i-1]+1 == nums[i-2]+2:\n",
    "                    f[i+1] = True\n",
    "        return f[n]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        nums_len = len(nums)\n",
    "        if nums_len==2:\n",
    "            return nums[0]==nums[1]\n",
    "        dp = [0]*(nums_len+1)\n",
    "        dp[2] = 2 if nums[0] == nums[1] else 0\n",
    "        dp[3] = 3 if dp[2] and nums[1] == nums[2] else 0\n",
    "        dp[3] = 3 if dp[3] or (nums[2]-nums[1]==1 and nums[1] - nums[0] ==1)  else 0\n",
    "        for i in range(4, nums_len+1):\n",
    "            if dp[i-2] and nums[i-1]==nums[i-2]:\n",
    "                dp[i]+=2\n",
    "            if dp[i-3] and ((nums[i-3]==nums[i-2] and nums[i-2]==nums[i-1]) or (nums[i-2]-nums[i-3]==1 and nums[i-1]-nums[i-2] == 1)  ):\n",
    "                dp[i]+=3\n",
    "            # dp[i] = (dp[i-2] and nums[i-1]==nums[i-2]) or (dp[i-3] or(dp[i-3] and ((nums[i-3]==nums[i-2] and nums[i-2]==nums[i-1]) or (nums[i-2]-nums[i-3]==1 and nums[i-1]-nums[i-2] == 1)  )))\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1]!=0 \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 压缩成0维3行\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        a, b, c, n = True, False, nums[0] == nums[1], len(nums)\n",
    "        for i in range(2,n): \n",
    "            a, b, c = b, c, (a and (nums[i] == nums[i-1] + 1 == nums[i-2] + 2 or nums[i] == nums[i-1] == nums[i-2])) or (b and nums[i] == nums[i-1])\n",
    "        return c\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return False \n",
    "        dp = [False]*len(nums)\n",
    "        # dp[0] = True \n",
    "        # dp[i]代表从i开始是否可以组成\n",
    "        if nums[0] == nums[1]:\n",
    "            dp[1] = True \n",
    "        if len(nums) == 2:\n",
    "            return dp[1]\n",
    "        \n",
    "        if nums[0] == nums[1] == nums[2] or nums[1] - nums[0] == nums[2]-nums[1] == 1:\n",
    "            dp[2] = True \n",
    "        \n",
    "        for i in range(3,len(nums)):\n",
    "            # 先判断2的\n",
    "            if nums[i] == nums[i-1]:\n",
    "                if dp[i-2]:\n",
    "                    dp[i] = True\n",
    "                    continue \n",
    "                if nums[i] == nums[i-2]:\n",
    "                    if dp[i-3]:\n",
    "                        dp[i] = True\n",
    "                        continue \n",
    "            if nums[i] - nums[i-1] == nums[i-1]-nums[i-2] == 1:\n",
    "                if dp[i-3]:\n",
    "                    dp[i] = True\n",
    "        print(dp)\n",
    "        return dp[len(dp)-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [False] * (n + 1)\n",
    "        f[0] = True\n",
    "        for i in range(1, n):\n",
    "            if (f[i - 1] and nums[i - 1] == nums[i]) or (i >= 2 and f[i - 2] and nums[i] == nums[i - 1] == nums[i - 2]) or (i >= 2 and f[i - 2] and nums[i] == nums[i - 1] + 1 and nums[i] == nums[i - 2] + 2):\n",
    "                f[i + 1] = True\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        l = len(nums)\n",
    "        dp = [False] * (l+1)\n",
    "        dp[0] = True\n",
    "        for i in range(2,l+1):\n",
    "            if len(set(nums[i-2:i])) == 1:\n",
    "                dp[i] = dp[i-2] or dp[i]\n",
    "            if i>2 and (len(set(nums[i-3:i])) == 1 or nums[i-3:i][2] - nums[i-3:i][1] == 1 and  nums[i-3:i][1] - nums[i-3:i][0] == 1):\n",
    "                dp[i] = dp[i-3] or dp[i]\n",
    "        return dp[l]\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(length):\n",
    "        #     if length ==0:\n",
    "        #         return True\n",
    "        #     if length < 0:\n",
    "        #         return False\n",
    "        #     ans = False\n",
    "        #     if length >=3 and (len(set(nums[length-3:length])) == 1 or nums[length-3:length][2] - nums[length-3:length][1] == 1 and  nums[length-3:length][1] - nums[length-3:length][0] == 1):\n",
    "        #         ans = ans or dfs(length-3)\n",
    "        #     if length >=2 and len(set(nums[length-2:length])) == 1:\n",
    "        #         ans = ans or dfs(length-2)\n",
    "        #     return ans\n",
    "        # return dfs(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(n):\n",
    "            #print(dp)\n",
    "            r1=i+2\n",
    "            r2=i+3\n",
    "            if r1<=(n):\n",
    "               \n",
    "                if len(set(nums[i:r1]))==1:\n",
    "                    #print(i,r1)\n",
    "                    dp[i+2]=dp[i+2]|dp[i]\n",
    "\n",
    "            if r2<=(n):        \n",
    "                if len(set(nums[i:r2]))==1:\n",
    "                    dp[i+3]=dp[i+3]|dp[i]\n",
    "                elif (nums[i]+1)==nums[i+1] and (nums[i+1]+1)==nums[i+2]:\n",
    "                    dp[i+3]=dp[i+3]|dp[i]\n",
    "            \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [False] * (n+1)\n",
    "        dp[0] = True\n",
    "        for i in range(1, n):\n",
    "            x = nums[i]\n",
    "            if dp[i-1] and x == nums[i-1]:\n",
    "                dp[i+1] = True\n",
    "            if i > 1:\n",
    "                if dp[i-2] and x == nums[i-1] == nums[i-2]:\n",
    "                    dp[i+1] = True\n",
    "                if dp[i-2] and x == nums[i-1]+1 == nums[i-2]+2:\n",
    "                    dp[i+1] = True\n",
    "            \n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        # dp[i]: can the first i nums be partitioned?\n",
    "        n = len(nums)\n",
    "        dp = [False] * (n + 1)\n",
    "        dp[0] = True\n",
    "        for i in range(2, n + 1):\n",
    "            if i == 2:\n",
    "                dp[i] = nums[i - 1] == nums[i - 2]\n",
    "            else:\n",
    "                if nums[i - 1] == nums[i - 2]:\n",
    "                    dp[i] = dp[i] or dp[i - 2]\n",
    "                if nums[i - 1] == nums[i - 2] and nums[i - 2] == nums[i - 3]:\n",
    "                    dp[i] = dp[i] or dp[i - 3]\n",
    "                if nums[i - 1] == nums[i - 2] + 1 and nums[i - 2] == nums[i - 3] + 1:\n",
    "                    dp[i] = dp[i] or dp[i - 3]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "            i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or \n",
    "            x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "                f[i + 1] = True\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        # f[i+1] 表示从 nums[0] 到 nums[i] 的这些元素能否有效划分\n",
    "        f = [False] * (len(nums) + 1)\n",
    "        f[0] = True\n",
    "        for i in range(len(f)-1):\n",
    "            f[i + 1] |= f[i - 1] and nums[i] == nums[i-1]\n",
    "            if i >= 2:\n",
    "                f[i + 1] |= f[i - 2] and nums[i] == nums[i-1] == nums[i-2]\n",
    "                f[i + 1] |= f[i - 2] and nums[i] == nums[i-1] + 1 == nums[i-2] + 2\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(1,n+1):\n",
    "            if i>=2 and nums[i-1]==nums[i-2]:\n",
    "                dp[i]|=dp[i-2]\n",
    "            if i>=3 and nums[i-2]==nums[i-1]==nums[i-3]:\n",
    "                dp[i]|=dp[i-3]\n",
    "            if i>=3 and nums[i-1]==nums[i-2]+1==nums[i-3]+2:\n",
    "                dp[i]|=dp[i-3]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i,x in enumerate(nums):\n",
    "            if i > 0 and f[i-1] and x == nums[i-1] or \\\n",
    "                i > 1 and f[i-2] and (x == nums[i-1] == nums[i-2] or \\\n",
    "                                        x == nums[i-1] + 1 == nums[i-2] + 2):\n",
    "                f[i+ 1] = True\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=1\n",
    "        for i in range (1,n):\n",
    "            if (nums[i]==nums[i-1] and dp[i-1]==1) or (i>=2 and nums[i]==nums[i-1] and nums[i-2]==nums[i-1] and dp[i-2]==1) or (i>=2 and nums[i]==nums[i-1]+1 and nums[i-2]+1==nums[i-1] and dp[i-2]==1):\n",
    "                dp[i+1]=1\n",
    "        return (dp[-1]==1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        dp=[False]*(n+1)\n",
    "        dp[0]=True\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1] and dp[i+1-2]:\n",
    "                dp[i+1]=True\n",
    "            if i-2>=0 and dp[i+1-3] and (nums[i]-nums[i-1]==nums[i-1]-nums[i-2]==1 or nums[i]==nums[i-1]==nums[i-2]):\n",
    "                dp[i+1] =True\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        # 题目已经告诉我了，划分型dp\n",
    "        # 划分型dp的题目应该如何考虑？\n",
    "        # dp[i] 代表从nums[0] - nums[i]是否是有效划分\n",
    "        # dp[i] (dp[i - 2] and 满足条件1) or (dp[i - 3] and 满足条件2) or (dp[i - 3] and 满足条件3)\n",
    "        n = len(nums)\n",
    "\n",
    "        f = [True] + [False] * n \n",
    "        for i , x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "                i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or \n",
    "                                        x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "\n",
    "                f[i + 1] = True\n",
    "\n",
    "        return f[n]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        if n < 2:\n",
    "            return False\n",
    "        f[2] = nums[0] == nums[1]\n",
    "        for i in range(2, n):\n",
    "            x = nums[i]\n",
    "            tmp = i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2)\n",
    "\n",
    "\n",
    "            f[i + 1] = tmp\n",
    "        print(f)\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        f = [True, False]\n",
    "        for i in range(1, len(nums)):\n",
    "            if f[-2] and nums[i] == nums[i - 1]:\n",
    "                f.append(True)\n",
    "            elif i > 1 and f[-3] and (nums[i] == nums[i - 1] == nums[i - 2] or nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "                f.append(True)\n",
    "            else:\n",
    "                f.append(False)\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        f=[False for i in range(n+1)]\n",
    "        f[0]=True\n",
    "        for i in range(1,n):\n",
    "            if i>1:\n",
    "                f[i+1]=(f[i-1] and nums[i]==nums[i-1])or(f[i-2] and nums[i]==nums[i-1]==nums[i-2])or(f[i-2] and nums[i-2]+2==nums[i-1]+1==nums[i])\n",
    "            else:\n",
    "                f[i+1]=f[i-1] and nums[i]==nums[i-1]\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [False] * (n+1)\n",
    "        dp[0] = True\n",
    "        if nums[0] == nums[1]:\n",
    "            dp[2] = True\n",
    "        \n",
    "        for i in range(3,n+1):\n",
    "            # check each criteria:\n",
    "            c1 = nums[i-1] == nums[i-2] and dp[i-2]\n",
    "            c2 = nums[i-1] == nums[i-2] == nums[i-3] and dp[i-3]\n",
    "            c3 = nums[i-1]-nums[i-2] == 1 and nums[i-2]-nums[i-3] == 1 and dp[i-3]\n",
    "            if c1 or c2 or c3:\n",
    "                dp[i] = True\n",
    "        print(dp)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validPartition(self, nums: List[int]) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        f = [True] + [False] * n\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\r\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\r\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\r\n",
    "               f[i + 1] = True\r\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef validPartition(self, nums: List[int]) -> bool:\n",
    "\t\tn = len(nums)\n",
    "\t\tres = [False for _ in range(n + 1)]\n",
    "\t\tres[0] = True\n",
    "\t\tfor i in range(1, n):\n",
    "\t\t\tif i >= 1 and res[i - 1] and nums[i] == nums[i - 1]:\n",
    "\t\t\t\tres[i + 1] = True\n",
    "\t\t\tif i >= 2 and res[i - 2]:\n",
    "\t\t\t\tif nums[i - 1] == nums[i] and nums[i - 1] == nums[i - 2]:\n",
    "\t\t\t\t\tres[i + 1] = True\n",
    "\t\t\t\telif nums[i - 1] + 1 == nums[i] and nums[i - 2] + 1 == nums[i - 1]:\n",
    "\t\t\t\t\tres[i + 1] = True\n",
    "\t\treturn res[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        dp = [False]*n\n",
    "        # dp[0]=\n",
    "        for i in range(1,n):\n",
    "            if i>2:\n",
    "                dp[i] = (nums[i-1]==nums[i] and dp[i-2]) or (nums[i-1]==nums[i]==nums[i-2] and dp[i-3]) or (nums[i-2]+1==nums[i-1] and nums[i-1]+1==nums[i] and dp[i-3])\n",
    "            elif i==2:\n",
    "                dp[i] = nums[i-1]==nums[i] and dp[i-2] or nums[i-1]==nums[i]==nums[i-2] or nums[i-2]+1==nums[i-1] and nums[i-1]+1==nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i-1]==nums[i]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [False for _ in range(n+1)]\n",
    "        dp[0] = True\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                dp[i+1] |= dp[i-1]\n",
    "            if i >= 2:\n",
    "                if (nums[i] == nums[i-1] and nums[i-1] == nums[i-2]) or (nums[i] == nums[i-1]+1 and nums[i-1] == nums[i-2]+1):\n",
    "                    dp[i+1] |= dp[i-2]\n",
    "        # print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        arr = [None for i in range(n+1)]\n",
    "        arr[0] = True \n",
    "        arr[1] = False \n",
    "        arr[2] = (nums[0] == nums[1])\n",
    "        for i in range(3, n+1):\n",
    "            if nums[i-1] == nums[i-2] and arr[i-2]:\n",
    "                arr[i] = True \n",
    "            elif nums[i-1] == nums[i-2] == nums[i-3] and arr[i-3]:\n",
    "                arr[i] = True \n",
    "            elif nums[i-1] == nums[i-2] + 1 == nums[i-3] + 2 and arr[i-3]:\n",
    "                arr[i] = True \n",
    "            else:\n",
    "                arr[i] = False \n",
    "        return arr[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        ans = [False for i in range(n+1)]\n",
    "        ans[0] = True\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == nums[i-1] and ans[i-1] ==True:\n",
    "                ans[i+1] = True\n",
    "            if i > 1:\n",
    "                if nums[i] == nums[i-1] == nums[i-2] and ans[i-2] == True:\n",
    "                    ans[i+1] = True\n",
    "                if nums[i] == nums[i-1]+1 == nums[i-2]+2 and ans[i-2] == True:\n",
    "                    ans[i+1] = True\n",
    "        return ans[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        \n",
    "        dp = [False for i in range(n+1)]\n",
    "        dp[0]=True\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i-1] and dp[i-1]:\n",
    "                dp[i+1] = True\n",
    "            if i > 1:\n",
    "                if nums[i] == nums[i-1] == nums[i-2] and dp[i-2]:\n",
    "                    dp[i+1]=True\n",
    "                if nums[i] - 1 == nums[i-1] == nums[i-2] + 1 and dp[i-2]:\n",
    "                    dp[i+1]=True\n",
    "            \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 2:\n",
    "            if nums[0] == nums[1]:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        dp = [False]*(n)\n",
    "        if nums[0] == nums[1]:\n",
    "            dp[1] = True\n",
    "        if nums[0] == nums[1] == nums[2] or nums[0]+2 == nums[1]+1 ==nums[2]:\n",
    "            dp[2] = True\n",
    "        for i in range(2, n):\n",
    "            if i > 1 and dp[i-2] and nums[i] == nums[i-1]:\n",
    "                dp[i] = True\n",
    "            if i > 2 and dp[i-3]:\n",
    "                if nums[i] == nums[i-1] == nums[i-2] or nums[i-2]+2==nums[i-1]+1==nums[i]:\n",
    "                    dp[i] = True\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if (i > 0 and dp[i -1] and nums[i] == nums[i - 1]) or (i > 1 and dp[i - 2] and nums[i] == nums[i - 1] == nums[i - 2]) or (i > 1 and dp[i - 2] and nums[i] == nums[i - 1] + 1 == nums[i -2] + 2):\n",
    "                dp[i + 1] = True\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [True] + [False]*n\n",
    "        for i in range(1, n):\n",
    "            if i > 0 and dp[i-1] and nums[i] == nums[i-1]:\n",
    "                dp[i+1] = True\n",
    "            if i > 1 and dp[i-2]:\n",
    "                if nums[i] == nums[i-1] == nums[i-2] or nums[i-2]+2==nums[i-1]+1==nums[i]:\n",
    "                    dp[i+1] = True\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        dp = [False] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            elif i == 1:\n",
    "                if nums[0] == nums[1]:\n",
    "                    dp[i] = True\n",
    "            elif i == 2:\n",
    "                if nums[0] == nums[1] and nums[1] == nums[2]:\n",
    "                    dp[i] = True\n",
    "                if nums[2] - nums[1] == 1 and nums[1] - nums[0] == 1:\n",
    "                    dp[i] = True\n",
    "            else:\n",
    "                if dp[i - 2] == True and nums[i] == nums[i - 1]:\n",
    "                    dp[i] = True\n",
    "                elif dp[i - 3] == True:\n",
    "                    if nums[i] == nums[i - 1] and nums[i] == nums[i - 2]:\n",
    "                        dp[i] = True\n",
    "                    elif nums[i] - nums[i - 1] == 1 and nums[i - 1] - nums[i - 2] == 1:\n",
    "                        dp[i] = True\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        def myfun1(start1,end1):\n",
    "            if end1-start1==2:\n",
    "                if nums[start1+1]==nums[end1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            elif end1-start1==3:\n",
    "                if nums[start1+1]==nums[start1+2] and nums[start1+2]==nums[start1+3]:\n",
    "                    return True\n",
    "                elif nums[start1+1]==nums[start1+2]-1 and nums[start1+2]==nums[start1+3]-1:\n",
    "                    return True\n",
    "                return False\n",
    "        \n",
    "        my_mat=[1]+[0]*len(nums)\n",
    "        my_mat[2]=(nums[0]==nums[1])\n",
    "\n",
    "        for i in range(2,len(nums)):\n",
    "            if myfun1(i-2,i) and my_mat[i-1]:\n",
    "                my_mat[i+1]=1\n",
    "            if myfun1(i-3,i) and my_mat[i-2]:\n",
    "                my_mat[i+1]=1\n",
    "\n",
    "        return my_mat[-1]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            \n",
    "            if i + 2 < n:\n",
    "                if nums[i]==nums[i+1]==nums[i+2] or nums[i] + 1 == nums[i + 1] == nums[i + 2] - 1:\n",
    "                    if dfs(i + 3):\n",
    "                        return True\n",
    "            if i + 1 < n:\n",
    "                if nums[i] == nums[i + 1]:\n",
    "                    if dfs(i + 2):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0)\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1] or \\\n",
    "               i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                       x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "               f[i + 1] = True\n",
    "        return f[n]\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [True] + [False] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            a = i > 0 and dp[i - 1] and x == nums[i - 1]\n",
    "            b =  i > 1 and dp[i - 2] and (x == nums[i - 1] == nums[i - 2] or x == nums[i - 1] + 1 == nums[i - 2] + 2)\n",
    "            dp[i + 1] = a | b\n",
    "        return dp[n]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [True] + [False] * n\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            # 检查是否可以形成长度为2的有效子数组\n",
    "            if i > 0 and f[i - 1] and x == nums[i - 1]:\n",
    "                f[i + 1] = True\n",
    "            # 检查是否可以形成长度为3的有效子数组\n",
    "            elif i > 1 and f[i - 2] and (x == nums[i - 1] == nums[i - 2] or\n",
    "                                        x == nums[i - 1] + 1 == nums[i - 2] + 2):\n",
    "                f[i + 1] = True\n",
    "                \n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return False \n",
    "        dp = [False]*len(nums)\n",
    "        if nums[0] == nums[1]:\n",
    "            dp[1] = True \n",
    "        if len(nums) == 2:\n",
    "            return dp[1]\n",
    "        \n",
    "        if nums[0] == nums[1] == nums[2] or nums[1] - nums[0] == nums[2]-nums[1] == 1:\n",
    "            dp[2] = True \n",
    "        \n",
    "        for i in range(3,len(nums)):\n",
    "            # 先判断2的\n",
    "            if nums[i] == nums[i-1]:\n",
    "                if dp[i-2]:\n",
    "                    dp[i] = True\n",
    "                    continue \n",
    "                if nums[i] == nums[i-2]:\n",
    "                    if dp[i-3]:\n",
    "                        dp[i] = True\n",
    "                        continue \n",
    "            if nums[i] - nums[i-1] == nums[i-1]-nums[i-2] == 1:\n",
    "                if dp[i-3]:\n",
    "                    dp[i] = True\n",
    "        return dp[len(dp)-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 3 for _ in range(n + 1)]\n",
    "        dp = [False] * (n + 1)\n",
    "        dp[0] = True\n",
    "        for i in range(2, n + 1):\n",
    "            if dp[i - 2] and nums[i - 1] == nums[i - 2]:\n",
    "                dp[i] = True\n",
    "            if i >= 3 and dp[i - 3] and (nums[i - 1] == nums[i - 2] == nums[i - 3]):\n",
    "                dp[i] = True\n",
    "            if i >= 3 and dp[i - 3] and (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2):\n",
    "                dp[i] = True\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return True\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if i == 1:\n",
    "                return nums[i] == nums[i-1]\n",
    "            a, b, c = nums[i], nums[i-1], nums[i-2]\n",
    "            if a == b and dfs(i - 2):\n",
    "                return True\n",
    "            if (a == b == c or a == b + 1 == c + 2) and dfs(i-3):\n",
    "                return True\n",
    "            return False\n",
    "        return dfs(len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        self.dp={}\n",
    "        return self.check(nums,0,n-1)\n",
    "\n",
    "    def check(self,nums,i,j):\n",
    "        if (i>j):\n",
    "            return True\n",
    "        if (i==j):\n",
    "            return False\n",
    "        if self.dp.get((i,j)) is not None:\n",
    "            return self.dp.get((i,j))==1\n",
    "        res=(nums[i]==nums[i+1] and self.check(nums,i+2,j))\n",
    "        if (i<j-1):\n",
    "            res=res or (nums[i]==nums[i+1] and nums[i+1]==nums[i+2] and self.check(nums,i+3,j)) or (nums[i]==nums[i+1]-1 and nums[i+1]==nums[i+2]-1 and self.check(nums,i+3,j))\n",
    "        self.dp[(i,j)]=res\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        self.nums=nums\n",
    "        n=len(self.nums)\n",
    "        self.dp={}\n",
    "        return self.check(0,n-1)\n",
    "\n",
    "    def check(self,i,j):\n",
    "        if (i>j):\n",
    "            return True\n",
    "        if (i==j):\n",
    "            return False\n",
    "        if self.dp.get((i,j)) is not None:\n",
    "            return self.dp.get((i,j))\n",
    "        res=(self.nums[i]==self.nums[i+1] and self.check(i+2,j))\n",
    "        if (i<j-1):\n",
    "            res=res or (self.nums[i]==self.nums[i+1] and self.nums[i+1]==self.nums[i+2] and self.check(i+3,j)) or (self.nums[i]==self.nums[i+1]-1 and self.nums[i+1]==self.nums[i+2]-1 and self.check(i+3,j))\n",
    "        self.dp[(i,j)]=res\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        self.dp={}\n",
    "        return self.check(nums,0,n-1)\n",
    "\n",
    "    def check(self,nums,i,j):\n",
    "        if (i>j):\n",
    "            return True\n",
    "        if (i==j):\n",
    "            return False\n",
    "        if self.dp.get((i,j)) is not None:\n",
    "            return self.dp.get((i,j))\n",
    "        res=(nums[i]==nums[i+1] and self.check(nums,i+2,j))\n",
    "        if (i<j-1):\n",
    "            res=res or (nums[i]==nums[i+1] and nums[i+1]==nums[i+2] and self.check(nums,i+3,j)) or (nums[i]==nums[i+1]-1 and nums[i+1]==nums[i+2]-1 and self.check(nums,i+3,j))\n",
    "        self.dp[(i,j)]=res\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "\n",
    "        @cache\n",
    "        def dfs(length):\n",
    "            if length ==0:\n",
    "                return True\n",
    "            if length < 0:\n",
    "                return False\n",
    "            ans = False\n",
    "            if length >=3 and (len(set(nums[length-3:length])) == 1 or nums[length-3:length][2] - nums[length-3:length][1] == 1 and  nums[length-3:length][1] - nums[length-3:length][0] == 1):\n",
    "                ans = ans or dfs(length-3)\n",
    "            if length >=2 and len(set(nums[length-2:length])) == 1:\n",
    "                ans = ans or dfs(length-2)\n",
    "            return ans\n",
    "        return dfs(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def validPartition(self, nums: List[int]) -> bool:\n",
    "#         nums.sort()\n",
    "#         n = len(nums)\n",
    "#         memo = {}\n",
    "#         def dfs(i):\n",
    "#             if i in memo:\n",
    "#                 return memo[i]\n",
    "#             if i == n:\n",
    "#                 return True\n",
    "#             res = False\n",
    "#             # for i in range(start, n): wrong!!!!!!\n",
    "#             if i + 1 < n and nums[i] == nums[i+1]:\n",
    "#                 res = dfs(i+2)\n",
    "#             # Check for subarray of size 3 with equal elements or consecutive increasing elements\n",
    "#             if i + 2 < n and (nums[i] == nums[i+1] == nums[i+2]  or nums[i]+1 == nums[i+1] == nums[i+2]-1):\n",
    "#                 res = res or dfs(i+3)\n",
    "         \n",
    "#             memo[i] = res\n",
    "#             return res\n",
    "#         return dfs(0)\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        dic = {}\n",
    "\n",
    "        def dfs(i) :\n",
    "            if i == len(nums):\n",
    "                return True\n",
    "\n",
    "            if i in dic:\n",
    "                return dic[i]\n",
    "            # we need to have atleast 2 elements to even check for condition\n",
    "            res = False\n",
    "            # checking for partitions with 2 elements\n",
    "            if i < len(nums) - 1 and nums[i] == nums[i+1] :\n",
    "                res = dfs(i+2)\n",
    "            # checking for partitions with 3 elements\n",
    "            if i < len(nums) - 2:\n",
    "                if nums[i] == nums[i+1] == nums[i+2]  or nums[i]+1 == nums[i+1] == nums[i+2]-1  :\n",
    "                    res = res or dfs(i+3)\n",
    "            \n",
    "            dic[i] = res\n",
    "            return res\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        # nums.sort() # SUPER WRONG. contiguous so no sort allowed\n",
    "        n = len(nums)\n",
    "        memo = {}\n",
    "        def dfs(i):\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            if i == n:\n",
    "                return True\n",
    "            res = False\n",
    "            # for i in range(start, n): wrong!!!!!!\n",
    "            if i + 1 < n and nums[i] == nums[i+1]:\n",
    "                res = dfs(i+2)\n",
    "            # Check for subarray of size 3 with equal elements or consecutive increasing elements\n",
    "            if i + 2 < n and (nums[i] == nums[i+1] == nums[i+2]  or nums[i]+1 == nums[i+1] == nums[i+2]-1):\n",
    "                res = res or dfs(i+3)\n",
    "         \n",
    "            memo[i] = res\n",
    "            return res\n",
    "        return dfs(0)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            \n",
    "            if i + 2 < n:\n",
    "                if nums[i]==nums[i+1]==nums[i+2] or nums[i] + 1 == nums[i + 1] == nums[i + 2] - 1:\n",
    "                    if dfs(i + 3):\n",
    "                        return True\n",
    "            if i + 1 < n:\n",
    "                if nums[i] == nums[i + 1]:\n",
    "                    if dfs(i + 2):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos):\n",
    "            if pos==n:return True\n",
    "            if pos+1>=n:return False\n",
    "            if pos+2<n and nums[pos]==nums[pos+1]==nums[pos+2]:\n",
    "                if dfs(pos+3):return True\n",
    "            if pos+2<n and nums[pos]==nums[pos+1]-1==nums[pos+2]-2:\n",
    "                if dfs(pos+3):return True\n",
    "            if nums[pos]==nums[pos+1]:\n",
    "                if dfs(pos+2):return True\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int) -> bool:\n",
    "            if i < 0: return True\n",
    "            ret1 = i > 0 and nums[i] == nums[i - 1] and dfs(i - 2)\n",
    "            ret2 = i > 1 and nums[i] == nums[i - 1] == nums[i - 2] and dfs(i - 3)\n",
    "            ret3 = i > 1 and nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2 and dfs(i - 3)\n",
    "            return ret1 or ret2 or ret3\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        ans=False\n",
    "        @cache\n",
    "        def check(idx:int):\n",
    "            nonlocal ans\n",
    "            if ans:\n",
    "                return\n",
    "            if idx==n:\n",
    "                ans=True\n",
    "                return\n",
    "            if idx+1>=n:\n",
    "                return\n",
    "            if idx+2<n and nums[idx]==nums[idx+1] and nums[idx+1]==nums[idx+2]:\n",
    "                check(idx+3)\n",
    "            if nums[idx]==nums[idx+1]:\n",
    "                check(idx+2)\n",
    "            if idx+2<n and nums[idx]==nums[idx+1]-1 and nums[idx+1]==nums[idx+2]-1:\n",
    "                check(idx+3)\n",
    "        check(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int) -> bool:\n",
    "            if i < 0: return True\n",
    "            ret1 = i > 0 and nums[i] == nums[i - 1] and dfs(i - 2)\n",
    "            ret2 = i > 1 and nums[i] == nums[i - 1] == nums[i - 2] and dfs(i - 3)\n",
    "            ret3 = i > 1 and nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2 and dfs(i - 3)\n",
    "            return ret1 or ret2 or ret3\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                return True\n",
    "            \n",
    "            res = False\n",
    "            if idx < n - 1 and nums[idx] == nums[idx + 1]:\n",
    "                res |= dfs(idx + 2)\n",
    "                if idx < n - 2 and nums[idx + 1] == nums[idx + 2]:\n",
    "                    res |= dfs(idx + 3)\n",
    "            if idx < n - 2 and nums[idx] + 1 == nums[idx + 1] and nums[idx + 1] + 1 == nums[idx + 2]:\n",
    "                res |= dfs(idx + 3)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def g(i):\n",
    "            if i==n:\n",
    "                return True\n",
    "            res =False\n",
    "            if i<n-2 and (nums[i]==nums[i+1]==nums[i+2] or nums[i]==(nums[i+1]-1)==(nums[i+2]-2)):\n",
    "                res=max(g(i+3),res)\n",
    "            if i<n-1 and nums[i]==nums[i+1]:\n",
    "                res=max(g(i+2),res)\n",
    "            return res\n",
    "        return g(0)                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def recur(start):\n",
    "            if start == len(nums):\n",
    "                return True\n",
    "            res = False\n",
    "            if start < len(nums)-1 and nums[start] == nums[start+1]:\n",
    "                res |= recur(start+2)\n",
    "                if res:\n",
    "                    return True\n",
    "            if start < len(nums)-2 and ((nums[start] == nums[start+1] == nums[start+2]) or (nums[start+2]-nums[start+1] == 1 == nums[start+1]-nums[start])):\n",
    "                res |= recur(start+3)\n",
    "                if res:\n",
    "                    return True\n",
    "            return False\n",
    "        return recur(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            ans = False\n",
    "            if i + 1 < n and nums[i] == nums[i+1]:\n",
    "                ans = ans or dfs(i + 2)\n",
    "            if i + 2 < n and (nums[i] == nums[i+1] == nums[i+2]):\n",
    "                ans = ans or dfs(i + 3)\n",
    "            if i + 2 < n and (nums[i+1] - nums[i] == 1 and nums[i+2] - nums[i+1] == 1):\n",
    "                ans = ans or dfs(i + 3)\n",
    "            return ans\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        l = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def helper(idx: int) -> bool:\n",
    "            \"\"\"\n",
    "            determine if nums[idx:] can be partitioned\n",
    "            \"\"\"\n",
    "            if idx == l:    return True\n",
    "            if l - idx < 2: return False\n",
    "\n",
    "            # 2 elements\n",
    "            if nums[idx] == nums[idx + 1] and helper(idx + 2):  return True\n",
    "\n",
    "            # 3 elements\n",
    "            if l - idx >= 3:\n",
    "                if nums[idx] == nums[idx + 1] == nums[idx + 2] or nums[idx] + 2 == nums[idx + 1] + 1 == nums[idx + 2]:\n",
    "                    if helper(idx + 3): return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        return helper(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            ans = 0\n",
    "            if i + 1 < n and nums[i] == nums[i + 1] and dfs(i + 2):\n",
    "                return True\n",
    "            if i + 2 < n and nums[i] == nums[i + 1] == nums[i + 2] and dfs(i + 3):\n",
    "                return True\n",
    "            if i + 2 < n and nums[i] + 1 == nums[i + 1] and nums[i + 1] + 1 == nums[i + 2]:\n",
    "                return dfs(i + 3)\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            if i + 1 < n and nums[i] == nums[i+1]:\n",
    "                if dfs(i+2):\n",
    "                    return True\n",
    "            if i + 2 < n and nums[i] == nums[i+1] == nums[i+2]:\n",
    "                if dfs(i+3):\n",
    "                    return True\n",
    "            if i + 2 < n and nums[i]+2 == nums[i+1]+1 == nums[i+2]:     \n",
    "                if dfs(i+3):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return True\n",
    "            ans = 0\n",
    "            if i + 1 < n and nums[i] == nums[i + 1] and dfs(i + 2):\n",
    "                return True\n",
    "            if i + 2 < n and nums[i] == nums[i + 1] == nums[i + 2] and dfs(i + 3):\n",
    "                return True\n",
    "            if i + 2 < n and nums[i] + 2 == nums[i + 1] + 1 == nums[i + 2]:\n",
    "                return dfs(i + 3)\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
